Image editing tools like Photoshop from Adobe Inc., Paint Shop Pro from JASC Inc. provide graphical user interfaces (GUIs) to the user for manipulating and editing parts or whole of an image. A user may mark regions in an image and do various kind of editing operations on selected regions. Operations like moving the region, deleting the region, rotating the region, scaling the size of the region (both increasing as well as reducing the size) and other such operations create blank areas in the modified image. By way of definition, an exposed pixel is one that belonged to the region manipulated by the user and because the pixel was either moved elsewhere or deleted, it now has no color value assigned to it, i.e., the exposed pixel is blank. Hence, image manipulation operations may lead to blank holes in the modified image which need to be filled in order to create a visually acceptable version of the modified image. Typically, a user desires to modify “objects” in an image and the image editing software may be supplemented with an automatic object-identification process (such as “magic wand” in Adobe Photoshop) to extract the objects in the image. In such cases the user then simply selects objects of interest in the image and proceeds to modify these. The automatic object-identification process may use various image segmentation schemes based on color and texture in the image.
Image pixels may also be exposed by automatic image manipulation and modification routines as disclosed by the inventors in the U.S. patent application Ser. No. 09/328,968 filed Jun. 9, 1999, for ‘An interactive framework for understanding users perception of multimedia data’ and U.S. patent application Ser. No. 09/407,434 filed Sep. 29, 1999 for “Efficient Modification Scheme for Learning User's Perception during Image Retrieval”.
One known technique is that of assigning a uniform color, e.g., white or black, uniformly to all the exposed pixels. Image editing software such as Adobe Photoshop may allow the user to select the color(s) to be used for filling and an automatic image modification method may use a predetermined color or one calculated based on image properties. It may also be possible to fill the region with some repetitive pattern. However, this often results in an unacceptable and nonrealistic image specially if the region surrounding the exposed hole has some repetitive color patterns. A uniform color or a fixed repetitive pattern does not maintain continuity in color values with the surrounding regions and the filled hole stands out artificially. Also, this color assignment is mostly manual in nature.
Thus, there is a need to assign color intensity values like RGB (red-green-blue) to fill the hole created in the image in a manner such that exposed region merges with the surrounding region, i.e. the background, naturally.
Prior-art methods have used a-priori information about shading, illumination, shadowing information to render fixed geometric shapes in an image as disclosed by the inventors in U.S. Pat. No. 5,136,664. Their algorithm renders objects in an image whereas this invention renders the background after an object has been removed.
A method for interpolating pixels is disclosed in U.S. Pat. No. 5,222,204 for “Pixel Interpolation in Perspective Space” which accounts for non-linearity of distance changes in the perspective projection of 3-D objects onto images.
In U.S. Pat. No. 4,815,009 for “Algorithm for filling an Image Outline” a method for converting a region defined by vectors into a set of trapezoids is disclosed.
Similarly, a method for modifying image content is presented in the U.S. Pat. No. 4,725,966 for “Image Modification.” Both these inventions, however, do not address the problems identified here.